{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "knapsack_problem_sqa.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyMu43TQBkH5pTaMAzy0ctz5",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/yskmt2018/quantum/blob/master/knapsack_problem_sqa.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jo9Pphxn-5VX"
      },
      "source": [
        "# Knapsack Problem with Simulated Quantum Annealing\n",
        "\n",
        "* This notebook was created and tested on Google Colaboratory. (2020/09)\n",
        "\n",
        "## Reference\n",
        "\n",
        "> https://openjij.github.io/OpenJijTutorial/build/html/ja/8-KnapsackPyqubo.html"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ucz9ter0LOgp",
        "outputId": "2a0c760f-2481-45e1-804c-c7ac035935a4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "!python -V\n",
        "!pip install --quiet pyqubo openjij"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Python 3.6.9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1n6Ac8ev_eKR"
      },
      "source": [
        "import random\n",
        "import pyqubo\n",
        "from openjij import SQASampler"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fcJaZydn_0t4"
      },
      "source": [
        "## Problem Settings\n",
        "\n",
        "* 各荷物の価格のリスト$c$と重量のリスト$w$がある。\n",
        "\n",
        "* 選んだ荷物の合計重量が、ナップサックの最大容量$W$以下となる制約を満たしながら、選んだ荷物の合計価格を最大化する。\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZOpPwkhVFc2V"
      },
      "source": [
        "def random_baggage(baggage_number):\n",
        "  c = {}\n",
        "  w = {}\n",
        "  for i in range(baggage_number):\n",
        "    c[i] = random.randrange(W/2, W)\n",
        "    w[i] = random.randrange(1, W/2)\n",
        "  \n",
        "  return c, w"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4XFfQRel_wNb",
        "outputId": "c53eae12-005b-42df-8228-25da54f5288a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        }
      },
      "source": [
        "# Knapsack Capacity\n",
        "W = 20\n",
        "# Baggage Number\n",
        "N = 10\n",
        "# c: Cost List, w: Weight List\n",
        "c, w = random_baggage(N)\n",
        "\n",
        "print('c : {}'.format(c))\n",
        "print('w : {}'.format(w))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "c : {0: 13, 1: 18, 2: 16, 3: 13, 4: 10, 5: 13, 6: 18, 7: 16, 8: 13, 9: 14}\n",
            "w : {0: 8, 1: 7, 2: 1, 3: 3, 4: 6, 5: 9, 6: 8, 7: 9, 8: 6, 9: 7}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B5NNUmSrKZUA"
      },
      "source": [
        "## Formulation\n",
        "\n",
        "* KP の目的関数及び制約条件を定式化し、QUBO（Quadratic Unconstrained Binary Optimization）式を構築する。\n",
        "\n",
        "* QUBO 式の構築には、OSS ライブラリ PyQUBO（[GitHub](https://github.com/recruit-communications/pyqubo), [Documentation](https://pyqubo.readthedocs.io/en/latest/)）を用いる。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bu5lou7vQtzX"
      },
      "source": [
        "### QUBO1: Objective Function\n",
        "\n",
        "* 目的関数：荷物の合計価格\n",
        "\n",
        "$$\n",
        "-\\sum^{N-1}_{\\alpha = 0} c_{\\alpha}x_{\\alpha}\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2Xys6ZK6Jg63"
      },
      "source": [
        "def build_objective(x):\n",
        "  H = - sum(c[a] * x[a] for a in range(N))\n",
        "  return H"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "a_h77zolR8R8"
      },
      "source": [
        "### QUBO2: Capacity rule\n",
        "\n",
        "* 制約条件：荷物の合計重量が、ナップサックの最大容量以下となる。\n",
        "\n",
        "$$\n",
        "w\\left(W - \\sum^{N-1}_{\\alpha = 0}w_{\\alpha}x_{\\alpha} - Y \\right)^2\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vxssc7voR1lY"
      },
      "source": [
        "def build_capacity_rule(x, y):\n",
        "  H = pyqubo.Constraint((W - sum(w[a] * x[a] for a in range(N)) - y)**2, 'w')\n",
        "  return H"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Wqji_vtBTx9b"
      },
      "source": [
        "### Hamiltonian\n",
        "\n",
        "* 目的関数及び制約条件からハミルトニアン H を以下のように定義する。\n",
        "\n",
        "$$\n",
        "H = -\\sum^{N-1}_{\\alpha = 0} c_{\\alpha}x_{\\alpha}\n",
        "+ w\\left(W - \\sum^{N-1}_{\\alpha = 0}w_{\\alpha}x_{\\alpha} - Y \\right)^2\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-yCsKZW_Tgj1"
      },
      "source": [
        "# Selected Baggage\n",
        "x = pyqubo.Array.create('x', shape=(N), vartype='BINARY')\n",
        "# Slack Variable\n",
        "y = pyqubo.LogEncInteger('y', 0, W)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LDd1xfFdU5L3"
      },
      "source": [
        "H = build_objective(x) + \\\n",
        "    pyqubo.Placeholder('w') * build_capacity_rule(x, y)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DcWkroPXU-9T"
      },
      "source": [
        "feed_dict = {'w': 1}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S8avaUdfVFCa"
      },
      "source": [
        "model = H.compile()\n",
        "qubo, constant = model.to_qubo(feed_dict=feed_dict)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OBROyyUKVJ8l"
      },
      "source": [
        "## Execute Quantum Annealing\n",
        "\n",
        "* Sampler と呼ばれるモジュールを生成し、構築した QUBO 式を渡すことで、量子アニーリングを実行する。\n",
        "\n",
        "* 結果は、Response オブジェクトとして返却される。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HsqUBrDkVp1-"
      },
      "source": [
        "### OpenJij\n",
        "\n",
        "* OpenJij（[GitHub](https://github.com/OpenJij/OpenJij), [Documentation](https://openjij.github.io/OpenJij_Documentation/build/html/), [Tutorial](https://openjij.github.io/OpenJijTutorial/build/html/ja/index.html)）\n",
        "\n",
        "* OSS として、量子アニーリングをシミュレートする SQA（Simulated Quantum Annealing）の Python 用 API を提供している。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7Hc7MIH-VINM"
      },
      "source": [
        "sampler = SQASampler(num_reads=10)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "b2_RwiENVTW0",
        "outputId": "108290b0-148e-46d4-94de-50b4d9d3c8db",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        }
      },
      "source": [
        "%%time\n",
        "response = sampler.sample_qubo(qubo)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CPU times: user 122 ms, sys: 714 µs, total: 123 ms\n",
            "Wall time: 128 ms\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fskNDnEkVWvH"
      },
      "source": [
        "### Take Solutions\n",
        "\n",
        "* Response オブジェクトに格納されている量子アニーリングの結果（解）を取り出す。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TFLKSKY_VU_b"
      },
      "source": [
        "def extract_samples(response):\n",
        "  solutions = []\n",
        "  energies = []\n",
        "  \n",
        "  for record in response.record:\n",
        "    sol, num_occ = record[0], record[2]\n",
        "    solution, broken, energy = model.decode_solution(dict(zip(response.variables, sol)), vartype='BINARY', feed_dict=feed_dict)\n",
        "    if len(broken) == 0:\n",
        "      solutions += [solution] * num_occ\n",
        "      energies += [energy] * num_occ\n",
        "  \n",
        "  return solutions, energies"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WiK3hohvVdSQ"
      },
      "source": [
        "solutions, energies = extract_samples(response)\n",
        "best_solution = solutions[energies.index(min(energies))]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gOgshJMHVg-d"
      },
      "source": [
        "### Print Knapsack\n",
        "\n",
        "* ナップサックに入れた荷物の合計価格と合計重量を表示する。\n",
        "\n",
        "* 先に設定した制約条件が満たされていることを確認してください。\n",
        "\n",
        "> 荷物の合計重量が、ナップサックの最大容量以下となる。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zz7ep4aTeCrV",
        "outputId": "1b091df8-cf96-4043-c720-90490896af84",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "baggage_name = [chr(b) for b in range(65, 65+N)]\n",
        "baggage_name"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LZCrF4AngyW-",
        "outputId": "f85d205c-6bf4-4781-fc57-32831ded3176",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 140
        }
      },
      "source": [
        "total_cost = 0\n",
        "total_weight = 0\n",
        "\n",
        "print('Selected Baggages:')\n",
        "for (k, v) in best_solution['x'].items():\n",
        "    if v == 1:\n",
        "        print(' {} cost={}, weight={}'.format(baggage_name[k], c[k], w[k]))\n",
        "        total_cost += c[k]\n",
        "        total_weight += w[k]\n",
        "\n",
        "print()\n",
        "print('Total Cost={}, Total Weight={}, Knapsack Capacity={}'.format(total_cost, total_weight, W))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Selected Baggages:\n",
            " B cost=18, weight=7\n",
            " C cost=16, weight=1\n",
            " D cost=13, weight=3\n",
            " G cost=18, weight=8\n",
            "\n",
            "Total Cost=65, Total Weight=19, Knapsack Capacity=20\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}